package hotLeetcode;

import java.util.*;

public class H09Leetcode438 {
    public List<Integer> findAnagrams(String s, String p) {

        List<Integer> result = new ArrayList<>();
        //获取范围
        int len = p.length();
        for (int i = 0; i < s.length(); i++) {
            for (int j = i; j < s.length(); j++) {
                if (j >s.length() - len || i > s.length() -len) {
                    break;
                }
                String sub = s.substring(j, j + len );
                boolean flag = isTrue(sub, p);
                if (flag) {
                    if (!result.contains(j)) {
                        result.add(j);
                    }
                }
            }



        }
        return result;

    }

    private boolean isTrue(String sub, String p) {
        char[] subC = sub.toCharArray();
        char[] pC = p.toCharArray();
        Arrays.sort(subC);
        Arrays.sort(pC);

        for (int i = 0; i < subC.length; i++) {
            if (subC[i] != pC[i]) {
                return false;
            }
        }
        return true;

    }

    public List<Integer> findAnagrams2(String s, String p) {
        List<Integer> result = new ArrayList<>();

        for (int left = 0; left < s.length(); left++) {
            int  right = left + p.length();
            if (left > s.length() - p.length()) {
                break;
            }
            String sub = s.substring(left, right);
            boolean flag = isTrue(sub, p);
            if (flag) {
                if (!result.contains(left )) {
                    result.add(left );

                }
            }
        }

        return result;
    }

    //滑动窗口
    public List<Integer> findAnagrams3(String s, String p) {
        List<Integer> result = new ArrayList<>();

        if (s == null || p == null || s.length() < p.length()) {
            return result;
        }

        // 使用哈希表来存储 p 中字符的频率
        Map<Character, Integer> pFreq = new HashMap<>();
        for (char c : p.toCharArray()) {
            pFreq.put(c, pFreq.getOrDefault(c, 0) + 1);
        }

        // 使用哈希表来存储当前窗口内字符的频率
        Map<Character, Integer> windowFreq = new HashMap<>();
        int left = 0, right = 0, matched = 0;

        while (right < s.length()) {
            char r = s.charAt(right);

            // 扩展窗口
            if (pFreq.containsKey(r)) {
                windowFreq.put(r, windowFreq.getOrDefault(r, 0) + 1);
                if (windowFreq.get(r).equals(pFreq.get(r))) {
                    matched++;
                }
            }
            right++;

            // 缩小窗口，直到窗口大小等于 p 的长度
            if (right - left == p.length()) {
                if (matched == pFreq.size()) {
                    result.add(left);
                }

                char l = s.charAt(left);
                if (pFreq.containsKey(l)) {
                    if (windowFreq.get(l).equals(pFreq.get(l))) {
                        matched--;
                    }
                    windowFreq.put(l, windowFreq.get(l) - 1);
                }
                left++;
            }
        }

        return result;

    }


    //定长滑动窗口
    public List<Integer> findAnagrams4(String s, String p) {
        int[] arrS = new int[26];
        int[] arrP = new int[26];
        List<Integer> result = new ArrayList<>();

        for (char c : p.toCharArray()) {
            arrP[c - 'a']++;
        }

        for (int right = 0; right < s.length(); right++) {
            arrS[s.charAt(right) - 'a']++;
            int left = right - p.length() + 1;
            if (left < 0) {
                continue;
            }

            if (Arrays.equals(arrS, arrP)) {
                result.add(left);
            }

            //移除left，让窗口右滑
            arrS[s.charAt(left) - 'a']--;



        }
        return result;


    }


    public static void main(String[] args) {
        String s = "abab";
        String p = "ab";
        H09Leetcode438 h09Leetcode438 = new H09Leetcode438();
        System.out.println(h09Leetcode438.findAnagrams4(s, p));


    }

}
